K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。
K-均值是一个迭代算法，假设我们想要将数据聚类成n个组，其方法为:
首先选择$K$个随机的点，称为聚类中心（cluster centroids）；
对于数据集中的每一个数据，按照距离$K$个中心点的距离，将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。
计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。 用$μ^1$,$μ^2$,...,$μ^k$ 来表示聚类中心，用$c^{(1)}$,$c^{(2)}$,...,$c^{(m)}$来存储与第$i$个实例数据最近的聚类中心的索引，K-均值算法的伪代码如下：
Repeat {
for i = 1 to m
c(i) := index (form 1 to K) of cluster centroid closest to x(i)
for k = 1 to K
μk := average (mean) of points assigned to cluster k
}算法分为两个步骤，第一个for循环是赋值步骤，即：对于每一个样例$i$，计算其应该属于的类。第二个for循环是聚类中心的移动，即：对于每一个类$K$，重新计算该类的质心。
K-均值算法也可以很便利地用于将数据分为许多不同组，即使在没有非常明显区分的组群的情况下也可以。
K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此 K-均值的代价函数（又称畸变函数 Distortion function）为：
$$J(c^{(1)},...,c^{(m)},μ_1,...,μ_K)=\dfrac {1}{m}\sum_\limits{i=1}^{m}\left|| X^{\left( i\right) }-\mu_c^{(i)}\right|| ^{2}$$其中${{\mu }_{{{c}^{(i)}}}}$代表与${{x}^{(i)}}$最近的聚类中心点。 我们的的优化目标便是找出使得代价函数最小的 $c^{(1)}$,$c^{(2)}$,...,$c^{(m)}$和$μ^1$,$μ^2$,...,$μ^k$：
回顾刚才给出的: K-均值迭代算法，我们知道，第一个循环是用于减小$c^{(i)}$引起的代价，而第二个循环则是用于减小${{\mu }_{i}}$引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数，不然便是出现了错误。
聚类参考资料：
1.相似度/距离计算方法总结
(1). 闵可夫斯基距离Minkowski/（其中欧式距离：$p=2$)
$dist(X,Y)={{\left( {{\sum\limits_{i=1}^{n}{\left| {{x}{i}}-{{y}{i}} \right|}}^{p}} \right)}^{\frac{1}{p}}}$
(2). 杰卡德相似系数(Jaccard)：
$J(A,B)=\frac{\left| A\cap B \right|}{\left|A\cup B \right|}$
(3). 余弦相似度(cosine similarity)：
$n$维向量$x$和$y$的夹角记做$\theta$，根据余弦定理，其余弦值为：
$cos (\theta )=\frac{{{x}^{T}}y}{\left|x \right|\cdot \left| y \right|}=\frac{\sum\limits_{i=1}^{n}{{{x}{i}}{{y}{i}}}}{\sqrt{\sum\limits_{i=1}^{n}{{{x}{i}}^{2}}}\sqrt{\sum\limits{i=1}^{n}{{{y}{i}}^{2}}}}$ (4). Pearson皮尔逊相关系数： ${{\rho }{XY}}=\frac{\operatorname{cov}(X,Y)}{{{\sigma }{X}}{{\sigma }{Y}}}=\frac{E[(X-{{\mu }{X}})(Y-{{\mu }{Y}})]}{{{\sigma }{X}}{{\sigma }{Y}}}=\frac{\sum\limits_{i=1}^{n}{(x-{{\mu }{X}})(y-{{\mu }{Y}})}}{\sqrt{\sum\limits_{i=1}^{n}{{{(x-{{\mu }{X}})}^{2}}}}\sqrt{\sum\limits{i=1}^{n}{{{(y-{{\mu }_{Y}})}^{2}}}}}$
Pearson相关系数即将$x$、$y$坐标向量各自平移到原点后的夹角余弦。
2.聚类的衡量指标
(1). 均一性：$p$
类似于精确率，一个簇中只包含一个类别的样本，则满足均一性。其实也可以认为就是正确率(每个 聚簇中正确分类的样本数占该聚簇总样本数的比例和)
(2). 完整性：$r$
类似于召回率，同类别样本被归类到相同簇中，则满足完整性;每个聚簇中正确分类的样本数占该 类型的总样本数比例的和
(3). V-measure:
均一性和完整性的加权平均
$V = \frac{(1+\beta^2)pr}{\beta^2p+r}$
(4). 轮廓系数
样本$i$的轮廓系数：$s(i)$
簇内不相似度:计算样本$i$到同簇其它样本的平均距离为$a(i)$，应尽可能小。
簇间不相似度:计算样本$i$到其它簇$C_j$的所有样本的平均距离$b_{ij}$，应尽可能大。
轮廓系数：$s(i)$值越接近1表示样本$i$聚类越合理，越接近-1，表示样本$i$应该分类到 另外的簇中，近似为0，表示样本$i$应该在边界上;所有样本的$s(i)$的均值被成为聚类结果的轮廓系数。
$s(i) = \frac{b(i)-a(i)}{max{a(i),b(i)}}$
(5). ARI
数据集$S$共有$N$个元素， 两个聚类结果分别是：
$X={{{X}{1}},{{X}{2}},...,{{X}{r}}},Y={{{Y}{1}},{{Y}{2}},...,{{Y}{s}}}$
$X$和$Y$的元素个数为：
$a={{{a}{1}},{{a}{2}},...,{{a}{r}}},b={{{b}{1}},{{b}{2}},...,{{b}{s}}}$
ri1
记：${{n}{ij}}=\left| {{X}{i}}\cap {{Y}_{i}} \right|$
$ARI=\frac{\sum\limits_{i,j}{C_{{{n}{ij}}}^{2}}-\left[ \left( \sum\limits{i}{C_{{{a}{i}}}^{2}} \right)\cdot \left( \sum\limits{i}{C_{{{b}{i}}}^{2}} \right) \right]/C{n}^{2}}{\frac{1}{2}\left[ \left( \sum\limits_{i}{C_{{{a}{i}}}^{2}} \right)+\left( \sum\limits{i}{C_{{{b}{i}}}^{2}} \right) \right]-\left[ \left( \sum\limits{i}{C_{{{a}{i}}}^{2}} \right)\cdot \left( \sum\limits{i}{C_{{{b}{i}}}^{2}} \right) \right]/C{n}^{2}}$
在PCA中，我们要做的是找到一个方向向量（Vector direction），当我们把所有的数据都投射到该向量上时，我们希望投射平均均方误差能尽可能地小。方向向量是一个经过原点的向量，而投射误差是从特征向量向该方向向量作垂线的长度。
下面给出主成分分析问题的描述：
问题是要将$n$维数据降至$k$维，目标是找到向量$u^{(1)}$,$u^{(2)}$,...,$u^{(k)}$使得总的投射误差最小。主成分分析与线性回顾的比较：
主成分分析与线性回归是两种不同的算法。主成分分析最小化的是投射误差（Projected Error），而线性回归尝试的是最小化预测误差。线性回归的目的是预测结果，而主成分分析不作任何预测。
线性回归的误差（垂直于横轴投影），主要成分分析的误差（垂直于红线投影）。
PCA将$n$个特征降维到$k$个，可以用来进行数据压缩，如果100维的向量最后可以用10维来表示，那么压缩率为90%。同样图像处理领域的KL变换使用PCA做图像压缩。但PCA 要保证降维后，还要保证数据的特性损失最小。
PCA技术的一大好处是对数据进行降维的处理。我们可以对新求出的“主元”向量的重要性进行排序，根据需要取前面最重要的部分，将后面的维数省去，可以达到降维从而简化模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。
PCA技术的一个很大的优点是，它是完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。
但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
PCA 减少$n$维到$k$维：
第一步是均值归一化。我们需要计算出所有特征的均值，然后令 $x_j= x_j-μ_j$。如果特征是在不同的数量级上，我们还需要将其除以标准差 $σ^2$。
第二步是计算协方差矩阵（covariance matrix）$Σ$： $\sum=\dfrac {1}{m}\sum^{n}_{i=1}\left( x^{(i)}\right) \left( x^{(i)}\right) ^{T}$
第三步是计算协方差矩阵$Σ$的特征向量（eigenvectors）:
在 Octave 里我们可以利用奇异值分解（singular value decomposition）来求解，[U, S, V]= svd(sigma)。
$$Sigma=\dfrac {1}{m}\sum^{n}_{i=1}\left( x^{(i)}\right) \left( x^{(i)}\right) ^{T}$$
对于一个 $n×n$维度的矩阵，上式中的$U$是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从$n$维降至$k$维，我们只需要从$U$中选取前$k$个向量，获得一个$n×k$维度的矩阵，我们用$U_{reduce}$表示，然后通过如下计算获得要求的新特征向量$z^{(i)}$: $$z^{(i)}=U^{T}_{reduce}*x^{(i)}$$
其中$x$是$n×1$维的，因此结果为$k×1$维度。注，我们不对方差特征进行处理。
训练集的方差为：$\dfrac {1}{m}\sum^{m}_{i=1}\left| x^{\left( i\right) }\right| ^{2}$
我们希望在平均均方误差与训练集方差的比例尽可能小的情况下选择尽可能小的$k$值。
如果我们希望这个比例小于1%，就意味着原本数据的偏差有99%都保留下来了，如果我们选择保留95%的偏差，便能非常显著地降低模型中特征的维度了。
我们可以先令$k=1$，然后进行主要成分分析，获得$U_{reduce}$和$z$，然后计算比例是否小于1%。如果不是的话再令$k=2$，如此类推，直到找到可以使得比例小于1%的最小$k$ 值（原因是各个特征之间通常情况存在某种相关性）。
还有一些更好的方式来选择$k$，当我们在Octave中调用“svd”函数的时候，我们获得三个参数：[U, S, V] = svd(sigma)。
其中的$S$是一个$n×n$的矩阵，只有对角线上有值，而其它单元都是0，我们可以使用这个矩阵来计算平均均方误差与训练集方差的比例： $$\dfrac {\dfrac {1}{m}\sum^{m}{i=1}\left| x^{\left( i\right) }-x^{\left( i\right) }{approx}\right| ^{2}}{\dfrac {1}{m}\sum^{m}{i=1}\left| x^{(i)}\right| ^{2}}=1-\dfrac {\Sigma^{k}{i=1}S_{ii}}{\Sigma^{m}{i=1}S{ii}}\leq 1%$$
也就是：$$\frac {\Sigma^{k}{i=1}s{ii}}{\Sigma^{n}{i=1}s{ii}}\geq0.99$$
在压缩过数据后，我们可以采用如下方法来近似地获得原有的特征：$$x^{\left( i\right) }{approx}=U{reduce}z^{(i)}$$
我谈论PCA作为压缩算法。在那里你可能需要把1000维的数据压缩100维特征，或具有三维数据压缩到一二维表示。所以，如果这是一个压缩算法，应该能回到这个压缩表示，回到你原有的高维数据的一种近似。
所以，给定的$z^{(i)}$，这可能100维，怎么回到你原来的表示$x^{(i)}$，这可能是1000维的数组？
PCA算法，我们可能有一个这样的样本。如图中样本$x^{(1)}$,$x^{(2)}$。我们做的是，我们把这些样本投射到图中这个一维平面。然后现在我们需要只使用一个实数，比如$z^{(1)}$，指定这些点的位置后他们被投射到这一个三维曲面。给定一个点$z^{(1)}$，我们怎么能回去这个原始的二维空间呢？$x$为2维，$z$为1维，$z=U^{T}{reduce}x$，相反的方程为：$x{appox}=U_{reduce}\cdot z$,$x_{appox}\approx x$。正交矩阵U的转置和逆一样
如你所知，这是一个漂亮的与原始数据相当相似。所以，这就是你从低维表示$z$回到未压缩的表示。我们得到的数据的一个之间你的原始数据 $x$，我们也把这个过程称为重建原始数据。
当我们认为试图重建从压缩表示 $x$ 的初始值。所以，给定未标记的数据集，您现在知道如何应用PCA，你的带高维特征$x$和映射到这的低维表示$z$。这个视频，希望你现在也知道如何采取这些低维表示$z$，映射到备份到一个近似你原有的高维数据。
假使我们正在针对一张 100×100像素的图片进行某个计算机视觉的机器学习，即总共有10000 个特征。
第一步是运用主要成分分析将数据压缩至1000个特征
然后对训练集运行学习算法
在预测时，采用之前学习而来的$U_{reduce}$将输入的特征$x$转换成特征向量$z$，然后再进行预测 注：如果我们有交叉验证集合测试集，也采用对训练集学习而来的$U_{reduce}$。
错误的主要成分分析情况：一个常见错误使用主要成分分析的情况是，将其用于减少过拟合（减少了特征的数量）。这样做非常不好，不如尝试正则化处理。原因在于主要成分分析只是近似地丢弃掉一些特征，它并不考虑任何与结果变量有关的信息，因此可能会丢失非常重要的特征。然而当我们进行正则化处理时，会考虑到结果变量，不会丢掉重要的数据。
另一个常见的错误是，默认地将主要成分分析作为学习过程中的一部分，这虽然很多时候有效果，最好还是从所有原始特征开始，只在有必要的时候（算法运行太慢或者占用太多内存）才考虑采用主要成分分析。